import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/18 20:10
 * @description n皇后问题，经典回溯 dfs, 强行暴力会增大时间复杂度，需要进行回溯
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solveNQueens(4);
    }
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        // 同一列上的皇后位置
        Set<Integer> columns = new HashSet<>();
        // 两个斜对角线的皇后位置
        Set<Integer> x1 = new HashSet<>();
        Set<Integer> x2 = new HashSet<>();
        backtrack(ans, queens, n, 0, columns, x1, x2);
        return ans;
    }

    /**
     * 回溯函数，添加限制条件
     * @param ans 返回类型
     * @param queens 皇后位置
     * @param n n个皇后
     * @param row 当前行
     * @param columns 同一列上的hashSet
     * @param x1 正斜上的hashSet
     * @param x2 反斜上的hashSet
     */
    public void backtrack(List<List<String>> ans, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> x1,
                          Set<Integer> x2) {
        if (row == n) {
            // 到达最后一行

            List<String> list = draw(queens, n);
            ans.add(list);
        }else {
            // 这里的i为第row行的所有列值i
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                // 正对角线上（从左上角到右下角类似的对角线—），行坐标和列坐标之间的差相等时，那么说明在同一条对角线上
                int positive = row - i;
                if (x1.contains(positive)) {
                    continue;
                }
                // 反对角线(从右上角到左下角方向的对角线），行坐标和列坐标之和相等时，说明同一条对角线上已经存在
                int negative = row + i;
                if(x2.contains(negative)) {
                    continue;
                }
                // row 行 i 列 放置皇后
                queens[row] = i;
                // 第 i 列不能在放置皇后了，加入columns中，
                columns.add(i);
                // 正对角线上不能放置皇后了，
                x1.add(positive);
                x2.add(negative);
                backtrack(ans, queens, n, row + 1, columns, x1, x2);
                // 如果无法回退，那么重置
                queens[row] = -1;
                columns.remove(i);
                x1.remove(positive);
                x2.remove(negative);
            }
        }
    }

    /**
     * 所有位置不冲突后，依照题意绘制
     * @param queens n个皇后的位置
     * @param n n
     * @return List<String>
     */
    public List<String> draw(int[] queens, int n) {
        List<String> board = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            // 一行中只有一个位置为皇后
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}
